package bfsalgorithm;

import java.util.*;

/**
 * 127、单词接龙
 */
public class Exercise7 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> visit = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for(String s : wordList) {
            hash.add(s);
        }

        if(!hash.contains(endWord)) {
            return 0;
        }

        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        visit.add(beginWord);
        int ret = 1; // 开始的字符也算一个长度

        while(!q.isEmpty()) {
            ret++;
            int size = q.size();
            while(size-- != 0) {
                String t = q.poll();
                for(int i = 0;i < t.length();i++) {
                    char[] tmp = t.toCharArray();
                    for(char ch = 'a';ch <= 'z';ch++) {
                        tmp[i] = ch;
                        String next = new String(tmp);
                        if(hash.contains(next) && !visit.contains(next)) {
                            if(next.equals(endWord)) {
                                return ret;
                            }
                            q.add(next);
                            visit.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
